package com.gxc.tree;

/**
 * 求完全二叉树节点的个数
 *
 * 解法：
 * a)递归
 * b)完全二叉树，根据左右子树的最左子节点高度，确定左右子树哪个是满二叉树，计算满二叉树的数量，另一边递归
 */
public class CompleteBinaryTree2 {

    public class Info {

        private int size;

        public Info(int size) {
            this.size = size;
        }
    }

    public int num(TreeBean head) {
        Info info = process(head);
        return info.size;
    }

    public Info process(TreeBean node) {
        if (node == null) return new Info(0);

        Info left = process(node.left);
        Info right = process(node.right);

        return new Info(left.size + right.size + 1);
    }

    public int process2(TreeBean node) {
        if (node == null) return 0;
        TreeBean left = node.left;
        TreeBean right = node.right;
        int lh = 0;
        int rh = 0;
        while (left != null) {
            lh++;
            left = left.left;
        }

        while (right != null) {
            rh++;
            right = right.right;
        }
        if (lh == rh) return (int) (Math.pow(2, lh) - 1);

        return 1 + process2(node.left) + process2(node.right);
    }

    public int num3(TreeBean head) {
        if (head == null) return 0;

        return process3(head, 1, mostLeftHeight(head, 1));
    }

    /**
     *
     * @param node
     * @param level  当前在第几层
     * @param height 总共高低
     * @return
     */
    public int process3(TreeBean node, int level, int height) {
        if (level == height) return 1;

        //X的右子树的最左深度与树的总深度一致，说明X的左子树是满二叉树
        if (mostLeftHeight(node.right, level+1) == height) {
            return (int) (Math.pow(2, height - level) + process3(node.right, level+1, height));
        } else {
            //X的右子树的最左深度与树的总深度不一致，说明X的右子树是满二叉树
            return (int) (Math.pow(2, height - level - 1) + process3(node.left, level+1, height));
        }
    }

    public int mostLeftHeight(TreeBean node, int level) {
        while (node != null) {
            level++;
            node = node.left;
        }
        return level-1;
    }
}
